package com.leo.algorithm.linked;

public class MergeTwo {
    public static void main(String[] args) {

    }
    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;

        while (p1 != null && p2 != null) {
            // 比较 p1 和 p2 两个指针
            // 将值较小的的节点接到 p 指针
            if (p1.getVal() > p2.getVal()) {
                p.setNext(p2);
                p2 = p2.getNext();
            } else {
                p.setNext(p1);
                p1 = p1.getNext();
            }
            // p 指针不断前进
            p = p.getNext();
        }

        if (p1 != null) {
            p.setNext(p1);
        }

        if (p2 != null) {
            p.setNext(p2);
        }

        return dummy.getNext();
    }

}
